package codeTop;

import java.util.HashMap;
import java.util.Map;


public class q138 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        Map<Node,Integer> map = new HashMap<>();
        Map<Integer,Node> map1 = new HashMap<>();
        Node p = head;
        int idx = 0;
        while (p != null) {
            map.put(p,idx);
            Node node = new Node(p.val);
            map1.put(idx,node);
            if (idx > 0) {
                map1.get(idx-1).next = node;
            }
            idx++;
            p = p.next;
        }
        p = head;
        Node p1 = map1.get(0);
        while (p != null) {
            if (p.random != null) {
                p1.random = map1.get(map.get(p.random));
            }
            p = p.next;
            p1 = p1.next;
        }
        return map1.get(0);
    }
}
